package oj;

import sun.awt.image.ImageWatched;

import java.util.*;

//前k个高频单词：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
public class Solution_692_2 {
    //方法2：使用优先级队列
    static class Cmp implements Comparator<Map.Entry<String,Integer>>{
        //按照此顺序进行比较大小：leetcode-1 < coding-1 < love-2 < i-2
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            String word1 = o1.getKey();
            int count1 = o1.getValue();

            String word2 = o2.getKey();
            int count2 = o2.getValue();

            if(count1 < count2){
                //o1 : leetcode-1
                //o2 : i-2
                //o1 < o2
                return -1;
            }else if(count1 > count2){
                //o1 : i-2
                //o2 : leetcode-1
                //o1 > o2
                return 1;
            }
            //count 相等时，进行 word 的比较
            //love < i
            //word1 = love
            //word2 = i
            //返回 负数
            return word2.compareTo(word1);
        }
    }
    public static List<String> topKFrequent(String[] words, int k){
        Map<String,Integer> countMap = new TreeMap<>();
        for(String w : words){
            int count = countMap.getOrDefault(w,0);
            countMap.put(w,count + 1);
        }
        //得到每个单词出现的次数
        //使用优先级队列完成
        //优先级队列中的元素类型也使用 Map.Entry<单词，次数>
        //优先级队列是小堆，越小越在堆顶
        //堆顶的元素是最容易先淘汰的
        //所以大小顺序为：leetcode-1 < coding-1 < love-2 < i-2
        Cmp comparator = new Cmp();
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(comparator);

        Set<Map.Entry<String,Integer>> entrySet = countMap.entrySet();
        //先遍历 entrySet ，把前K个放入优先级队列
        //之后的，再一一和堆顶元素进行比较
        int n = 0;
        for(Map.Entry<String,Integer> entry : entrySet){
            if(n < k){
                queue.offer(entry);
            }else{
                //后边的
                //比较 entry 和堆顶元素的大小
                int cmp = comparator.compare(entry,queue.peek());
                if(cmp > 0){
                    queue.poll();
                    queue.offer(entry);
                }
            }
            n++;
        }
        //目前优先级队列中维护的是k个候选人
        //假如 k = 2
        //堆顶 love-2          i-2 堆底
        //queue.poll() 先出来的是 love-2 然后，i-2 再出来
        //所以使用头插的方式将结果插入到 List 中
        //Linkedlist 的头插时间复杂度比 ArrayList 的低
        List<String> ans = new LinkedList<>();
        while (!queue.isEmpty()){
            Map.Entry<String,Integer> entry = queue.poll();
            String word = entry.getKey();
            ans.add(0,word);
        }
        return ans;
    }
}
